#include <iostream>
using namespace std;
#include "stdio.h"
#include "stdlib.h"
#define TRUE  1
#define FALSE  0
#define OK 1
#define ERROR  0
#include <iostream>
using namespace std;
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
typedef int KeyType;
typedef int SElemType;
typedef struct BSTNode
{
    SElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

typedef BSTNode ElemType;

typedef struct Sqstack
{
   BSTree *top;
   BSTree *base;
   SElemType stacksize;
}Sqstack;

SElemType InitStack(Sqstack &T)
{
    T.base=(BSTree*)malloc(STACK_INIT_SIZE *sizeof(BSTree));
    if(!T.base) exit(0);
    T.top=T.base;
    T.stacksize=STACK_INIT_SIZE;
    return OK;
}

SElemType Push(Sqstack &S,BSTree P)
{
    if(S.top-S.base>=S.stacksize)
	{
		S.base=(BSTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BSTree));
		if(!S.base) return ERROR;
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=P;
	return OK;
}

SElemType Pop(Sqstack &S,BSTree &P)
{
    if(S.base==S.top) return ERROR;
    S.top--;
    P=*S.top;
    return OK;
}

BSTree SearchBST(BSTree T,KeyType key)
{
    if((!T)||T->data==key) return T;
    else if(key<T->data) return SearchBST(T->lchild,key);
    else  return SearchBST(T->rchild,key);
}

void DeleteBST(BSTree &T,KeyType key)
{
   BSTree p=T,f=NULL,q=NULL,s=NULL;
   while(p)
   {
       if(p->data==key) break;
       f=p;
       if(p->data>key) p=p->lchild;
       else p=p->rchild;
   }
   if(!p) return ;
   q=p;
   if((p->lchild)&&(p->rchild))
   {
       s=p->lchild;
       while(s->rchild)
       {
           q=s;
           s=s->rchild;
       }
       p->data=s->data;
       if(q!=p)
       q->rchild=s->lchild;
       else q->lchild=s->lchild;
       delete s;
       return ;
   }
   else if(!p->rchild)
   {
       p=p->lchild;
   }
   else if(!p->lchild)
   {
       p=p->rchild;
   }
   if(!f) T=p;
   else if(q==f->lchild) f->lchild=p;
   else f->rchild=p;
   delete q;
}
void CreatBST(BSTree &T,SElemType e)
{
    if(!T)
    {
        BSTree S;
        S=new BSTNode;
        S->data=e;
        S->lchild=S->rchild=NULL;
        T=S;
    }
    else if(e<T->data)
        CreatBST(T->lchild,e);
    else CreatBST(T->rchild,e);
}

void InOrderTraverse1(BSTree T)
{
    if(T)
    {
        InOrderTraverse1(T->lchild);
        printf("%d ",T->data);
        InOrderTraverse1(T->rchild);
    }
}
void XnOrderTraverse(BSTree T)
{
    if(T)
    {
        printf("%d ",T->data);
        XnOrderTraverse(T->lchild);
        XnOrderTraverse(T->rchild);
    }
}
void HnOrderTraverse(BSTree T)
{
    if(T)
    {
        HnOrderTraverse(T->lchild);
        HnOrderTraverse(T->rchild);
        printf("%d ",T->data);
    }
}
SElemType StacEmpty(Sqstack S)
{
    if(S.top==S.base)
        return 1;
    else return 0;
}
void InOrderTraverse2(BSTree T)
{
   Sqstack S;
   InitStack(S);
   BSTree p=T,q;
   q=new BSTNode;
   while(p||!StacEmpty(S))
   {
       if(p)
       {
           Push(S,p);
           p=p->lchild;
       }
       else
       {
           Pop(S,q);
           printf("%d ",q->data);
           p=q->rchild;
       }
   }

}
typedef struct
{
    BSTree *base;
    int front;
    int rear;
}SqQueue;

SElemType InitQueue(SqQueue &q)
{
   q.base=new BSTree[STACK_INIT_SIZE];
   if(!q.base) exit(0);
   q.front=q.rear=0;
   return OK;
}

SElemType EnQueue(SqQueue &q,BSTree p)
{
    if((q.rear+1)%STACK_INIT_SIZE==q.front) return ERROR;
    q.base[q.rear]=p;
    q.rear=(q.rear+1)%STACK_INIT_SIZE;
    return OK;
}

SElemType DeQueue(SqQueue &q,BSTree &p)
{
    if(q.front==q.rear) return ERROR;
    p=q.base[q.front];
    q.front=(q.front+1)%STACK_INIT_SIZE;
    return OK;
}

SElemType QueueEmpty(SqQueue q)
{
    if(q.front==q.rear) return 1;
    else return 0;
}

int BinaryTreeLevelOrder(BSTree root)
{
    SqQueue q;
    //树为空，直接返回
    if (root == NULL)
    {
        return 1;
    }
    InitQueue(q);
    //先将根节点入队
    EnQueue(q,root);
    while (!QueueEmpty(q))
    {
        BSTree p;
        //出队保存队头并访问
        DeQueue(q,p);
        printf("%d ", p->data);
        //将出队结点的左子树根入队
        if (p->lchild)
            EnQueue(q,p->lchild);
        //将出队结点的右子树根入队
        if (p->rchild)
            EnQueue(q,p->rchild);
     }
       return OK;
}

int Depth(BSTree T)
{
    if(T==NULL) return 0;
    else
    {
        int n,m;
        n=Depth(T->lchild);
        m=Depth(T->rchild);
    if(n>m) return (n+1);
    else return (m+1);
    }
}

int NodeCount(BSTree T)
{

    if(T->lchild==NULL||T->rchild==NULL) return 1;
    else return NodeCount(T->lchild)+NodeCount(T->rchild);
}

int J(BSTree &T)
{
    if(T==NULL) return 0;
    else
    {
      BSTree p;
      p=new BSTNode;
      p=T->lchild;
      T->lchild=T->rchild;
      T->rchild=p;
      J(T->lchild);
      J(T->rchild);
    }
    return OK;
}

int main()
{
  int n,i,k;
  BSTNode *T;
  T=NULL;
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
      cin>>k;
      CreatBST(T,k);
  }
  XnOrderTraverse(T);
  printf("\n");
  InOrderTraverse1(T);
  printf("\n");
  HnOrderTraverse(T);
  printf("\n");
  scanf("%d",&n);
  if(SearchBST(T,n)) printf("1\n");
  else printf("0\n");
  scanf("%d",&n);
  if(SearchBST(T,n)) printf("1\n");
  else printf("0\n");
  scanf("%d",&n);
  CreatBST(T,n);
  XnOrderTraverse(T);
  printf("\n");
  InOrderTraverse1(T);
  printf("\n");
  HnOrderTraverse(T);
  printf("\n");
  InOrderTraverse2(T);
  printf("\n");
  BinaryTreeLevelOrder(T);
  printf("\n");
  J(T);
  XnOrderTraverse(T);
  printf("\n");
  InOrderTraverse1(T);
  printf("\n");
  HnOrderTraverse(T);
  printf("\n");
  J(T);
  XnOrderTraverse(T);
  printf("\n");
  InOrderTraverse1(T);
  printf("\n");
  HnOrderTraverse(T);
  printf("\n");
  printf("%d\n",Depth(T));
  printf("%d\n",NodeCount(T));
  scanf("%d",&n);
  //DeleteBST(T,n);
  //HnOrderTraverse(T);
}
